//Implement strStr(). 
//
// Return the index of the first occurrence of needle in haystack, or -1 if need
//le is not part of haystack. 
//
// Clarification: 
//
// What should we return when needle is an empty string? This is a great questio
//n to ask during an interview. 
//
// For the purpose of this problem, we will return 0 when needle is an empty str
//ing. This is consistent to C's strstr() and Java's indexOf(). 
//
// 
// Example 1: 
// Input: haystack = "hello", needle = "ll"
//Output: 2
// Example 2: 
// Input: haystack = "aaaaa", needle = "bba"
//Output: -1
// Example 3: 
// Input: haystack = "", needle = ""
//Output: 0
// 
// 
// Constraints: 
//
// 
// 0 <= haystack.length, needle.length <= 5 * 104 
// haystack and needle consist of only lower-case English characters. 
// 
// Related Topics 双指针 字符串 
// 👍 889 👎 0


package leetcode.editor.cn;

//Java：Implement strStr()
class P28ImplementStrstr {
    public static void main(String[] args) {
        Solution solution = new P28ImplementStrstr().new Solution();
        // TO TEST
        System.out.println(solution.strStr("hellofdsfsfsdf", "fdsf"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //1.暴力破解
        int strStrBr(String haystack, String needle) {
            int n = haystack.length(), m = needle.length();
            for (int i = 0; i + m <= n; i++) {
                boolean flag = true;
                for (int j = 0; j < m; j++) {
                    if (haystack.charAt(i + j) != needle.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    return i;
                }
            }
            return -1;
        }

        //2.与一类似
        public int strStr(String haystack, String needle) {
            if (needle == null || needle.equals("")) {
                return 0;
            }
            //找到第一字母，后面位置固定
            char first = needle.charAt(0);
            for (int start = 0; start + needle.length() <= haystack.length(); start++) {
                if (haystack.charAt(start) == first) {
                    int i = start + 1, j = 1;
                    while (i < haystack.length() && j < needle.length()) {
                        if (needle.charAt(j) == haystack.charAt(i)) {
                            i++;
                            j++;
                        } else {
                            break;
                        }
                    }
                    if (j == needle.length()) {
                        return i - needle.length();
                    }
                }
            }

            return -1;
        }

        //3.前缀表
        public int strStrPrefix(String haystack, String needle) {
            int n = haystack.length(), m = needle.length();
            if (m == 0) {
                return 0;
            }
            int[] pi = new int[m];
            for (int i = 1, j = 0; i < m; i++) {
                while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                    j = pi[j - 1];
                }
                if (needle.charAt(i) == needle.charAt(j)) {
                    j++;
                }
                pi[i] = j;
            }
            for (int i = 0, j = 0; i < n; i++) {
                while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                    j = pi[j - 1];
                }
                if (haystack.charAt(i) == needle.charAt(j)) {
                    j++;
                }
                if (j == m) {
                    return i - m + 1;
                }
            }
            return -1;
        }
        public   int strStrOlder(String haystack, String needle) {
            if( needle == null || needle.length() == 0){
                return 0;
            }

            if (haystack == null || haystack.length() == 0 ) {
                return -1;
            }
            /*   return  haystack.indexOf(haystack, needle);*/
            int index = 0;
            int firstAppearane  = -1;
            for (int i = 0; i <haystack.length() ; i++) {
                if(index<needle.length()&&haystack.charAt(i)==needle.charAt(index)){

                    if (firstAppearane == -1) {
                        firstAppearane=i;

                    }
                    index++;
                }
                if (index==needle.length()&&i - firstAppearane == index-1) {
                    return firstAppearane;
                }
                if (i - firstAppearane == index - 1) {
                    continue;
                }else{
                    i = firstAppearane+1;
                    index=0;
                    firstAppearane=-1;
                }


            }
            return  -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}